package com.hy.backtracking3;

import java.util.ArrayList;
import java.util.List;

public class Sudoku {

    /**
     * 37. 解数独
     * 力扣题目链接
     *
     * 编写一个程序，通过填充空格来解决数独问题。
     *
     * 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
     * 答案被标成红色。
     * 提示：
     * 给定的数独序列只包含数字 1-9 和字符 '.' 。
     * 你可以假设给定的数独只有唯一解。
     * 给定数独永远是 9x9 形式的。
     *
     * 思路
     * 棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。
     *
     * 怎么做二维递归呢？
     *
     * 大家已经跟着「代码随想录」刷过了如下回溯法题目，例如：77.组合（组合问题），131.分割回文串（分割问题），78.子集（子集问题），46.全排列（排列问题），以及51.N皇后（N皇后问题），其实这些题目都是一维递归。
     *
     * 如果以上这几道题目没有做过的话，不建议上来就做这道题哈！
     *
     * N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
     *
     * 本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
     *
     * 因为这个树形结构太大了，我抽取一部分，如图所示：
     *
     *
      * @param board
     */
    public void solveSudoku(char [][] board){
        boolean res = solveSudokuHelper(board);
        System.out.println(res);
    }
    public boolean solveSudokuHelper(char [][] board){
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 跳过原始数据
                if (board[i][j] != '.'){
                    continue;
                }
                // (i, j) 这个位置放k是否合适
                for (char k = '1'; k <= '9'; k++) {
                    if (isValidSudoku(i,j,k,board)){
                        board[i][j] = k;
                        // 如果找到合适一组立刻返回
                        if (solveSudokuHelper(board)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」

            }
        }
//        System.out.println(Array2List(board));
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }
    /**
     *   判断棋盘是否合法有如下三个维度:
     *   同行是否重复
     *   同列是否重复
     *   9宫格里是否重复
     * @param row
     * @param col
     * @param val
     * @param board
     * @return
     */
    private boolean isValidSudoku(int row,int col,char val,char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++) {
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }

    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    public static void main(String[] args) {
        char [] [] board = {
                {'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}
        };

        Sudoku sudoku = new Sudoku();
        sudoku.solveSudoku(board);
        System.out.println(sudoku.Array2List(board));

    }
}
